package cn.bellychang.leetcode.question088;

/**
 * Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
 * <p>
 * The number of elements initialized in nums1 and nums2 are m and n respectively.
 * You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.
 *
 * @author ChangLiang
 * @date 2021/1/30
 */
public class Solution {

    // 时间复杂度 O(m * n)
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int arrayLength = m;
        for (int i = 0; i < n; i++) {
            doInsert(nums1, arrayLength, nums2[i]);
            arrayLength++;
        }
    }

    /**
     * @param arr          已排序数组
     * @param insertionVal 待插入value
     * @return
     */
    private void doInsert(int[] arr, int arrLength, int insertionVal) {
        for (int i = arrLength - 1; i >= 0; i--) {
            if (arr[i] <= insertionVal) {
                arr[i + 1] = insertionVal;
                return;
            } else {
                arr[i + 1] = arr[i];
            }
        }
        arr[0] = insertionVal;
    }
}
